package day05;

import java.io.IOException;

public class BinaryTree {
    char root;
    BinaryTree left;
    BinaryTree right;

    public BinaryTree(char root) {
        this.root = root;
        this.left = null;
        this.right = null;
    }

    public BinaryTree(char root, BinaryTree left, BinaryTree right) {
        this.root = root;
        this.left = left;
        this.right = right;
    }

    void preVisit() {
        System.out.print(this.root);
        if (left != null)
            left.preVisit();
        if (right != null)
            right.preVisit();

    }

    void postVisit() {

        if (left != null)
            left.postVisit();
        if (right != null)
            right.postVisit();
        System.out.print(this.root);

    }

    static BinaryTree createTree(String pre, String mid) {
        if (pre.length() == 0) return null;
        if (pre.length() == 1)
            return new BinaryTree(pre.charAt(0));

        BinaryTree tree = new BinaryTree(pre.charAt(0));
        int pos = mid.indexOf(pre.charAt(0));
        String lmid = mid.substring(0, pos);
        String rmid = mid.substring(pos + 1);
        String lpre = "", rpre = "";
        for (int i = 0; i < pre.length(); i++) {
            if (lmid.indexOf(pre.charAt(i)) >= 0)
                lpre += pre.charAt(i);
            if (rmid.indexOf(pre.charAt(i)) >= 0)
                rpre += pre.charAt(i);
        }
        tree.left = createTree(lpre, lmid);
        tree.right = createTree(rpre, rmid);

        return tree;
    }

    public static void main(String[] args) {
        BinaryTree b = new BinaryTree('B');
        BinaryTree c = new BinaryTree('C');
        BinaryTree a = new BinaryTree('A', b, c);
        //a.preVisit();
        BinaryTree tree = createTree("ABFCDGHEI", "BFAGDHCIE");
        tree.postVisit();

    }
}